package offer;

public class offerII_0019 {
    public boolean validPalindrome(String s) {
        int len=s.length();
        int left=0;
        int right=len-1;
        return dp(0,len-1,true,s);
    }
    public boolean dp(int left,int right,boolean flag,String s){
        if(left>=right) return true;
        if(flag){
            if(s.charAt(left)==s.charAt(right)){
                return dp(left+1,right-1,flag,s);
            }
            else{
                return dp(left+1,right,false,s)||dp(left,right-1,false,s);
            }
        }
        else{
            if(s.charAt(left)==s.charAt(right)){
                return dp(left+1,right-1,flag,s);
            }
            else{
                return false;
            }
        }
    }
}
